// 插入排序
pub fn insert_sort(mut v: Vec<i32>) -> Vec<i32> {
    if v.len() <= 1 {
        return v;
    }

    // 因为rust中操作索引的类型为usize ,usize天生为非负数，所以需要用i32作为中间类型过渡，以便让减1操作能通过编译
    for j in 1..v.len() {
        let key = v[j];
        let mut i = j as i32 - 1;
        while i >= 0 && v[i as usize] > key {
            v[i as usize + 1] = v[i as usize];
            i -= 1;
        }
        v[(i + 1) as usize] = key;
    }
    v
}

// 选择排序 (冒泡排序)
pub fn selected_sort(mut v: Vec<i32>) -> Vec<i32> {
    if v.len() <= 1 {
        return v;
    }

    for i in 0..v.len() {
        for j in i + 1..v.len() {
            if v[j] < v[i] {
                let tmp = v[i];
                v[i] = v[j];
                v[j] = tmp;
            }
        }
    }

    v
}

// 归并排序
pub fn merge_sort(mut v: &[i32]) -> Vec<i32> {
    if v.len() <= 1 {
        return Vec::from(v);
    }

    let q = v.len() / 2;
    let v1 = merge_sort(&v[..q]);
    let v2 = merge_sort(&v[q..]);
    merge(v1.as_slice(), v2.as_slice())
}

// 合并2个已排序的数组
pub fn merge(v1: &[i32], v2: &[i32]) -> Vec<i32> {
    let size = v1.len() + v2.len();
    let mut result = Vec::with_capacity(size);
    let mut i = 0;
    let mut j = 0;

    for _ in 0..size {
        match (i < v1.len(), j < v2.len()) {
            (true, false) => {
                result.push(v1[i]);
                i += 1;
            }
            (false, true) => {
                result.push(v2[j]);
                j += 1;
            }
            (true, true) => {
                if v1[i] < v2[j] {
                    result.push(v1[i]);
                    i += 1;
                } else {
                    result.push(v2[j]);
                    j += 1;
                }
            }
            (false, false) => {}
        }
    }

    result
}

#[test]
fn test_insert_sort() {
    let mut v = vec![3, 1, 4, 5, 2, 6];
    let result = insert_sort(v);
    assert_eq!(vec![1, 2, 3, 4, 5, 6], result);
}

#[test]
fn test_selected_sort() {
    let mut v = vec![3, 1, 4, 5, 2, 6];
    let result = selected_sort(v);
    assert_eq!(vec![1, 2, 3, 4, 5, 6], result);
}

#[test]
fn test_merge() {
    let v1 = [1, 5, 10];
    let v2 = [3, 4];
    assert_eq!(vec![1, 3, 4, 5, 10], merge(&v1, &v2));
}

#[test]
fn test_merge_sort() {
    let v = [3, 1, 4, 5, 2, 6];
    let result = merge_sort(&v);
    assert_eq!(vec![1, 2, 3, 4, 5, 6], result);
}
